#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    TreeNode *_hot = nullptr;
    void searchAt(TreeNode *root, int val)
    {
        if (root == nullptr)
            return;
        _hot = root;
        auto pivot = root->val;
        if (val < pivot)
            searchAt(root->left, val);
        else
            searchAt(root->right, val);
    }
    TreeNode *insertIntoBST(TreeNode *root, int val)
    {
        TreeNode *ptr = new TreeNode(val);
        searchAt(root, val);
        if (_hot == nullptr)
            return ptr;
        if (_hot->val < val)
            _hot->right = ptr;
        else
            _hot->left = ptr;
        return root;
    }
};